import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description: leetcode.中等题.K次增加后的最大乘积
 */

class Solution {
    public static int maximumProduct(int[] nums, int k) {
        //ans是每次一个数需要增加的数值
        int ans = 0;
        //结果，必须定义成long，int太小，在计算的时候可能会出现溢出
        long sum = 1;
        //定义数组统计相邻两数之间的差值
        int[] flag = new int[nums.length - 1];
        //先把数组从小到大排序
        Arrays.sort(nums);
        //统计相邻数直接的差值
        for(int i = 0; i < nums.length - 1; i++) {
            flag[i] = nums[i + 1] - nums[i];
        }
        //按照整块儿来增加数值
        //我们要保证每次增加都是给最小的增加
        //原因：(x + 1) / x == 1 + 1 / x
        //即当 x 越小时，增加的倍数越大
        for(int i = 0; i < nums.length - 1; i++) {
            //k == 0直接退出
            if(k == 0) {
                break;
            }
            //flag[i] == 0 表示相邻两个位置的差值为0，不需要补平
            if(flag[i] == 0) {
                continue;
            }
            //k / (i + 1) != 0 是计算是否能给数组前 (i + 1) 个数每个数都至少 + 1
            //如果等于0，表示无法整块增加数值，直接结束循环
            if(k / (i + 1) != 0) {
                //之间( k 能整块儿增加的数) 与 (nums[i + 1] - nums[i])选小的
                //保证前 i + 1 个数要么增加不到 nums[i + 1] 的值
                //要么最多和 nums[i + 1] 相等
                if(k / (i + 1) < flag[i]) {
                    ans = k / (i + 1);
                } else {
                    ans = flag[i];
                }
                for(int l = 0; l < i + 1; l++) {
                    nums[l] += ans;
                }
                k -= (i + 1) * ans;
            } else {
                break;
            }
        }
        //把剩下的不够一个整块的 k 逐个增加
        //或者是循环结束，数组的每个数都相同了，那么直接逐个增加1
        int i = 0;
        while(k != 0) {
            i %= nums.length;
            nums[i++] += 1;
            k--;
        }
        for(int x : nums) {
            sum = sum * x % 1000000007;
        }
        return (int)sum;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{24,5,64,53,26,38};
        int sum = maximumProduct(nums,54);
    }
}

public class Test {
}
